package com.cskaoyan.javase.recursion._1basic;

/**
 * 递归的思想
 * 案例: 求n的阶乘
 * 可以有两种方式:
 * 1.用循环求解
 * n! = n * (n-1) * (n-2) * ... * 1
 * 用循环求解最重要的是找到循环的条件和循环体,那么循环就很容易写出来
 *
 * 2.用递归求解
 * 用递归,最重要的是找到递归体和递归的出口
 * 找到递归体,就需要去用递归的思想思考问题,也就是尝试去把大规模的问题分解成小规模的问题
 * 当问题的规模足够小时,可以直接得出结果,这个结果就是递归的出口
 * n! = n * (n-1)!
 * (n-1)! = (n-1) * (n-2)!
 * ...
 * 1! = 1
 * 递归体就是n! = n * (n-1)!
 * 递归的出口是1! = 1
 *
 * 写递归先写出口,再写递归体
 *
 * 通过这个案例总结递归的优缺点
 * 优点:
 *      1.递归写出来的代码往往比较简洁
 *      2.递归的思想是非常符合人类解决问题的思想的.就是分解的思想.所以在求解问题时,如果使用递归,往往会比较好理解
 *
 * 缺点:
 *      1.递归很危险,容易栈溢出
 *      2.递归需要频繁调用方法,耗费栈内存空间
 *      而且递归在方法调用的过程中会有大量的重复计算,运算效率很低
 *      总结起来就是又慢又占内存(时空复杂度都不优越)
 *
 * 总结,递归是一个有鲜明缺点的求解方法,但它还是很有魅力的,很多问题如果不用递归求解是很困难的,是不太容易想到的.
 *
 * @since 17:10
 * @author wuguidong@cskaoyan.onaliyun.com
 */
public class Demo {
    public static void main(String[] args) {
        System.out.println(factorial(5));
        System.out.println(factorial2(5));
    }

    // 循环求解n的阶乘
    public static long factorial(int n) {
        long result = 1;
        while (n > 0) {
            result *= n;
            n--;
        }
        return result;
    }

    public static long factorial2(int n) {
        if (n == 1) {
            return 1;
        }
        return n * factorial2(n - 1);
    }
}
